00100	OFF ECHO;
00200	
00300	COMMENT  Functions for computing the irreducible characters
00400	of the symmetric group.;
00500	
00600	COMMENT  preds(part,m,n)  is the list of partitions of  n
00700	that can be obtained from  part (a partition of n) by deleting
00800	m  dots from the shape in a regular way.  See 
00900	(Littlewood 1950) p. 69 for the definition of the regular
01000	application of  m  nodes to a graph.  In these functions a
01100	partition is represented by a list of the summands
01200	in decreasing order.  In  pred(part,m,n), each member is
01300	preceded by  P  or  N  according to whether the
01400	application required is positive or negative.  We have, for
01500	example
01600		pred((5 3 3 2 2 1 1 1),2,18) = ((P 3 3 3 2 2 1 1 1)
01700	(N 5 2 2 2 2 1 1 1) (N 5 3 3 1 1 1 1 1) (N 5 3 3 2 2 1)).
01800	preds  has  mera  and  predsa  as auxiliary functions.;
01900	
02000	PREDS(PART,M,N) ←
02100		IF N < M OR NULL PART THEN NIL
02200		ELSE APPEND(PREDSA(PART,M,N),
02300			MERA(CAR PART,PREDS(CDR PART,M,N - CAR PART)));
02400	
02500	MERA(X,U) ←
02600		IF NULL U THEN NIL
02700		ELSE (CAAR U . (X . CDAR U)) . MERA(X,CDR U);
02800	
02900	PREDSA(PART,M,N) ←
03000		IF N < M OR NULL PART THEN NIL
03100		ELSE IF NULL CDR PART THEN
03200			(IF CAR PART - M = 0 THEN LIST LIST 'P
03300			ELSE LIST LIST('P ,CAR PART - M))
03400		ELSE  IF CAR PART - M > CADR PART - 1 
03500			THEN LIST('P . ((CAR PART - M) . CDR PART))
03600		ELSE IF CAR PART - M = CADR PART - 1 THEN NIL
03700		ELSE (LAMBDA Z;
03800			IF NULL Z THEN NIL
03900			ELSE IF CAAR Z EQ 'P THEN
04000				(IF (CADR PART - 1) = 0 THEN '((N))
04100				ELSE LIST('N . ((CADR PART - 1) . CDAR Z)))
04200			ELSE (IF (CADR PART - 1) = 0 THEN '((P))
04300				ELSE LIST('P . ((CADR PART - 1) . CDAR Z))))
04400			PREDSA(CDR PART,
04500				M - CAR PART + CADR PART - 1,
04600				N - CAR PART);
04700	
04800	COMMENT  After this, the computation of the characters
04900	is almost trivial.;
05000	
05100	CHI(PARTITION,CLASS) ←
05200		IF NULL PARTITION OR NULL CDR PARTITION THEN 1
05300		ELSE CHISUM(PREDS(PARTITION,CAR CLASS,SUMA CLASS),CDR CLASS);
05400	
05500	CHISUM(U,CLASS) ←
05600		IF NULL U THEN 0
05700		ELSE (IF CAAR U EQ 'P THEN 1 ELSE -1)*CHI(CDAR U,CLASS)
05800			+ CHISUM(CDR U,CLASS);
05900	
06000	SUMA U ← IF NULL U THEN 0 ELSE CAR U + SUMA CDR U;